FPGAs are frequently used for telecommunication. An essential aspect of telecommunication is the ability to route information from any source to any desired destination. A crossbar switch accomplishes this purpose.
FIG. 1 shows a simple crossbar switch. Eight input lines IN0 through IN7 carry input signals and eight output lines OUT0 through OUT7 provide output signals. An array of connectors can be selectively turned on to provide any of the input signals as an output signal. For example, turning on connector C0,0 connects input line IN0 to output line OUT0. Turning on connector C0,7 connects input line IN0 to output line OUT7. It is important that an output line not be driven by more than one input signal so that no contention occurs, and for this reason, crossbar switches are often implemented as multiplexers.
FIG. 2 shows a multiplexer implementation of the crossbar switch of FIG. 1, in which multiplexer control signals select one and only one of the input signals to provide as an output signal. For example, multiplexer control signals A0 select which of the eight input signals IN0 through IN7 will be provided as output signal OUT0.
As the number of input and output signals increases, the size of the crossbar switch becomes larger in proportion to the product of the number of input and output signals. For example, an array accommodating 1000 input signals and 1000 output signals would require a million connectors. If implemented with multiplexers, the crossbar switch would require 1000 multiplexers, each with 1000 input signals. U.S. Pat. No. 6,288,568 to Bauer and Young entitled “FPGA Architecture With Deep Look-Up Table RAMs” describes an FPGA architecture having lookup tables that can generate a function of eight input signals.
FIG. 3 is a copy of FIG. 20 of the Bauer and Young patent and represents one configurable logic block (CLB) of an FPGA. One possible function that can be generated by this flexible structure is a multiplexer. In FIG. 3, the lookup tables are 4-input lookup tables (LUTs), and thus each LUT can implement a 2-input multiplexer. The inputs applied on three of the lines F1, F2, F3, and F4 or G1, G2, G3, and G4 to each 4-input LUT are two multiplexer data inputs and one multiplexer control input. Eight lookup tables are present in the CLB of FIG. 3, each labeled LUT-F or LUT-G.
To form a conventional crossbar switch, the LUTs are each configured to implement a 2-input multiplexer with these three inputs. Sixteen data signals can be applied to these eight LUTs, two to each LUT. The lowest order multiplexer control bit C0 is applied to all eight LUTs and serves as the control bit for each of the eight 2:1 multiplexers. The next lowest order control bit C1 is applied to each of four multiplexers labeled F5, which receive outputs from pairs of the LUTs. Thus the outputs of the F5 multiplexers are 4:1 multiplexer outputs. Pairs of the F5 multiplexers feed F6 multiplexers as controlled by control bit C2, and pairs of the F6 multiplexers feed the F7 multiplexer as controlled by control bit C3. The F7 multiplexer thus provides the output of a 16:1 multiplexer. Another structure the same as FIG. 3 but receiving 16 different input signals receives the same control signals C0 through C3. The F8 multiplexer receives input signals from two F7 multiplexers and is controlled by a still higher order control bit C4 to produce a 32:1 multiplexer output signal. Thus an adjacent pair of CLBs can implement a 32:1 multiplexer.
Of course, providing these data and control signals requires routing through the FPGA. This routing has not been shown because it is easy to understand that the necessary route for each signal is formed by programmably connecting together the interconnect lines to get the data and control input signals from their origins and to get the output signals to their destinations.
Still wider multiplexer functions are formed by using another level of hierarchy. For example, a 1024:1 multiplexer can be formed in a very large FPGA by configuring 32 additional pairs of CLBs to each implement a 32:1 multiplexer, then finally forming a higher level structure, also from two CLBs, in which the input signals are the F8 output signals from the 32 pairs of CLBS. Thus the output of this final structure is the output of a 1024:1 multiplexer, and has consumed 64+2 CLBs or 66 CLBS. A square crossbar switch (1024 inputs and 1024 outputs) would require 1024 of these structures or a total of 67,584 CLBs.
One of the largest FPGA available from Xilinx Inc. today has on the order of 8,000 CLBS, so such a switch can not be implemented this way in such an FPGA but would require about 9 FPGAs.
It would be desirable to implement a large crossbar switch in an FPGA in a manner that is denser than this prior art implementation, preferably one that will fit into a single FPGA.